/**
 * @author LKQ
 * @date 2022/1/1 10:42
 * @description 深度优先遍历，先遍历一个结点，然后接着深入直到遍历无重复结点退回。 深度优先一般用到递归。
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        solution2.floodFill(image, 1, 1, 2);
    }


    int[][] dirs = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if (currColor != newColor) {
            dfs(image, sr, sc, currColor, newColor);
        }
        return image;
    }

    public void dfs(int[][] image, int x, int y, int color, int newColor) {
        if (image[x][y] == color) {
            image[x][y] = newColor;
            for (int i = 0; i < 4; i++) {
                int mx = x + dirs[i][0], my = y + dirs[i][1];
                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
                    dfs(image, mx, my, color, newColor);
                }
            }
        }
    }
}
